package day10;

/**
 * 输入某二叉树的前序遍历和中序遍历的结果，
 * 请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 * 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，
 * 则重建二叉树并返回。
 * <p>
 * Created by Administrator on 2017/1/9.
 */
public class Test01 {
    public static void main(String[] args) {
//        int[] pre = new int[]{1, 2, 4, 7, 3, 5, 6, 8};
//        int[] in = new int[]{4, 7, 2, 1, 5, 3, 8, 6};

//        int[] pre = new int[]{1, 2, 3, 4};
//        int[] in = new int[]{4, 3, 2, 1};
//        int[] in = new int[]{1, 2, 3, 4};


        int[] pre = new int[]{0, 1, 3, 7, 8, 4, 9, 10, 2, 5, 11, 12, 6, 13, 14};
        int[] in = new int[]{7, 3, 8, 1, 9, 4, 10, 0, 11, 5, 12, 2, 13, 6, 14};
        TreeNode node = reConstructBinaryTree(pre, in);
        System.out.println(node);
    }

    public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if (pre.length == 0) {
            return null;
        }
        if (pre.length == 1) {
            return new TreeNode(pre[0]);
        }

        int rVal = pre[0];
        for (int j = 0; j < pre.length; j++) {
            if (in[j] == rVal) {
                int[] lIn = new int[j];
                int[] rIn = new int[in.length - j - 1];
                System.arraycopy(in, 0, lIn, 0, j);
                System.arraycopy(in, j + 1, rIn, 0, in.length - j - 1);

                int[] lPre = new int[j];
                int[] rPre = new int[in.length - j - 1];
                System.arraycopy(pre, 1, lPre, 0, j);
                System.arraycopy(pre, j + 1, rPre, 0, in.length - j - 1);

                TreeNode node = reConstructBinaryTree(lPre, lIn);
                TreeNode root = new TreeNode(rVal);
                createNode(in, rVal, j, root, node);

                TreeNode node2 = reConstructBinaryTree(rPre, rIn);
                createNode(pre, rVal, j, root, node2);
                return root;
            }
        }
        return null;
    }

    private static void createNode(int[] pre, int rval, int j, TreeNode root, TreeNode node2) {
        if (node2 != null && pre[0] == rval) {
            root.right = node2;
        } else if (node2 != null && pre[j] == rval) {
            root.left = node2;
        }
    }
}
